package lib

import "algorithms/ds"

func init() {
	Probs = append(Probs, Problem{
		Num:         86,
		Discription: "按照指定值分隔链表",
		Level:       2,
		Labels: map[string]int{
			"链表":    1,
			"双指针滑动": 1,
		},
	})
}

//  维护两个链表，一个存比指定值小的，一个存比指定值大的，最后连起来
func PartitionList(head *ds.ListNode, x int) *ds.ListNode {
	if head == nil {
		return nil
	}

	smallerPreHead := &ds.ListNode{
		Next: nil,
	}
	biggerPreHead := &ds.ListNode{
		Next: nil,
	}
	temp1 := smallerPreHead
	temp2 := biggerPreHead

	for head != nil {
		if head.Val < x {
			temp1.Next = head
			temp1 = temp1.Next
		} else {
			temp2.Next = head
			temp2 = temp2.Next
		}
		head = head.Next
	}

	temp1.Next = biggerPreHead.Next
	temp2.Next = nil
	return smallerPreHead.Next
}
